home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / freeWAIS-sf-1.1 / ir / trie.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-05-19  |  6.0 KB  |  324 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4. */
  5.  
  6. /* Copyright (c) CNIDR (see ../COPYRIGHT) */
  7.  
  8.  
  9. #ifndef lint
  10. static char *RCSid = "$Header: /usr/local/ls6/src+data/src/freeWAIS-0.2-sf/ir/RCS/trie.c,v 1.4 1994/05/20 12:57:46 pfeifer Exp $";
  11. #endif
  12.  
  13. /* Change log:
  14.  * $Log: trie.c,v $
  15.  * Revision 1.4  1994/05/20  12:57:46  pfeifer
  16.  * beta
  17.  *
  18.  * Revision 1.3  1994/03/23  15:30:58  pfeifer
  19.  * fixed iso code
  20.  *
  21.  * Revision 1.2  1994/03/08  21:06:44  pfeifer
  22.  * Patchlevel 04
  23.  *
  24.  * Revision 1.1  1993/02/16  15:05:35  freewais
  25.  * Initial revision
  26.  *
  27.  * Revision 1.2  92/02/12  13:52:49  jonathan
  28.  * Added "$Log" so RCS will put the log message in the header
  29.  * 
  30.  * 
  31. */
  32.  
  33. /*
  34.   trie.c: This module provides an associative lookup table, based on
  35.   tries [see Knuth,D. Art of Computer Programming, Vol 3]
  36.  
  37.   Author: Simon E Spero (ses@ccgr.technion.ac.il)
  38.   This file is in the public domain.
  39.  
  40.   public functions:
  41.   
  42.   encode: encodes a string for searching
  43.  
  44.   make_trie_allocator: contructs a trie allocator
  45.   dispose_trie_allocator: dispose of a trie
  46.  
  47.   new_trie(string): 
  48.     creates a new trie containing only the entry `string'
  49.     
  50.   trie_lookup(word,dictionary,allocator).
  51.    This function looks up word in the dictionary, and, if found,
  52.    returns a pointer to it's datum. If the word is not found,
  53.    and allocator != NULL, the word will be added to the dictionary.
  54.    If an error occurs, the function returns NULL
  55. */
  56.   
  57.  
  58. /* #include <stdio.h> */
  59. #include "cutil.h"
  60. #include <ctype.h>
  61. #include "trie.h"
  62.  
  63. /*
  64.  * Special purpose allocators for resources that are freed only in bulk
  65.  */
  66.  
  67. /*
  68.  * make a new allocator 
  69.  */
  70. allocator* make_allocator(item_size,free_func) 
  71. int item_size;
  72. void (*free_func)();
  73. {
  74.   allocator* tmp;
  75.   if (!(tmp = (allocator *)s_malloc(sizeof(allocator)))) {
  76.     return 0L;
  77.   }
  78.  
  79.   tmp->size=item_size;
  80.   tmp->dispose = free_func;
  81.   return tmp;
  82. }
  83.  
  84. /*
  85.  * dispose of an allocator
  86.  */
  87. void fast_free(alloc)
  88. allocator* alloc;
  89. {
  90.   
  91.   char *block;
  92.   int i,j;
  93.   int limit;
  94.   for(i=0;i<alloc->blocks_allocated;i++) {
  95.     if(alloc->dispose) {
  96.       block=alloc->tofree[i];
  97.       limit = (i+1 == alloc->blocks_allocated ? CHUNK_SIZE - alloc->items_left : CHUNK_SIZE);
  98.       for(j=0;j<limit;j++) {
  99.     alloc->dispose(block);
  100.     block += alloc->size;
  101.       }
  102.     }
  103.     free(alloc->tofree[i]);
  104.   }
  105. }
  106.  
  107. /*
  108.  * allocate an item
  109.  */
  110.  
  111. char* fast_alloc(alloc)
  112. allocator* alloc;
  113. {
  114.   
  115.   char* tmp;
  116.  
  117.   if (!alloc->items_left) {
  118.     if (alloc->blocks_allocated <MAX_BLOCKS &&
  119.     (tmp = (char *)s_malloc(alloc->size*CHUNK_SIZE))) {
  120.       alloc->tofree[alloc->blocks_allocated++] = tmp;
  121.       alloc->next_location = tmp +alloc->size;
  122.       alloc->items_left = CHUNK_SIZE-1;
  123.       return tmp;
  124.     } else {
  125.       return 0L;
  126.     }
  127.   } else {
  128.     tmp = alloc->next_location;
  129.     alloc->next_location += alloc->size;
  130.     alloc->items_left--;
  131.     return tmp;
  132.   }
  133. }
  134.  
  135. /*
  136.  * function to free non fast_alloced stuff from a trie.
  137.  *   should really be a lambda expression, but....
  138.  */
  139.  
  140. void  free_trie(dict)
  141. trie* dict;
  142. {
  143.   free(dict->string);
  144. }
  145.  
  146. /*
  147.  * make an allocator for tries
  148.  */
  149.  
  150. trie_allocator* make_trie_allocator()
  151. {
  152.   trie_allocator* tmp;
  153.   if(!(tmp = (trie_allocator*)s_malloc(sizeof(trie_allocator)))) {
  154.     return 0L;
  155.   }
  156.   if (!(tmp->tries = make_allocator(sizeof(trie),free_trie))) {
  157.     free(tmp);
  158.     return 0L;
  159.   }
  160.   if(!(tmp->trie_tables = make_allocator(sizeof(trie_table),0L))) {
  161.     free(tmp->tries);
  162.     free(tmp);
  163.     return 0L;
  164.   }
  165.   return tmp;
  166. }
  167.  
  168. /*
  169.  * dispose of a trie
  170.  */
  171.  
  172. void dispose_trie_allocator(alloc)
  173. trie_allocator* alloc;
  174. {
  175.   fast_free(alloc->tries);
  176.   fast_free(alloc->trie_tables);
  177.   free(alloc);
  178. }
  179.  
  180. /*
  181.  * make a trie with str as it's only entry
  182.  */
  183.  
  184. trie* new_trie(str,alloc)
  185. char* str;
  186. trie_allocator* alloc;
  187. {
  188.   trie* tmp;
  189.  
  190.   tmp=(trie*)fast_alloc(alloc->tries);
  191.   tmp->string=s_strdup(str);
  192.   tmp->table=0L;
  193.   tmp->datum=0L;
  194.   return tmp;
  195. }
  196.  
  197. trie ** new_trie_table(alloc)
  198. allocator* alloc; {
  199.  
  200.   trie** tmp;
  201.  
  202.   tmp=(trie **)fast_alloc(alloc);
  203.   if(!tmp) {
  204.     return 0L;
  205.   }
  206.   return tmp;
  207. }
  208.  
  209. /*
  210.   After all those allocators, finally a useful function! 
  211.   */
  212.  
  213. void **trie_lookup(key,dict,alloc)
  214.      char* key;
  215.      trie* dict;
  216.      trie_allocator* alloc;
  217. {
  218.  
  219.   char *c,*d;
  220.   trie *t,*t2;
  221.  
  222.   c = key;
  223.   d = dict->string;
  224.  
  225.   while(*c && *d && *c == *d) {
  226.     c++; d++;
  227.   }
  228.  
  229.   if (!*c ) { 
  230.     if(!*d) {
  231.       /* we found the answer*/
  232.       return &(dict->datum);
  233.     }
  234.     /* key was a prefix*/
  235.     if (!alloc) {
  236.       return 0L;
  237.     }
  238.     /* split this node */
  239.     t = new_trie(d+1,alloc);
  240.     t->table = dict->table;
  241.     t->datum = dict->datum;
  242.     dict->table= (trie **)new_trie_table(alloc->trie_tables);
  243.     dict->table[*d]=t;
  244.     dict->datum=0L;
  245.     dict->string=s_strdup(key);
  246.     return &(dict->datum);
  247.   }
  248.  
  249.   if(*d && *c != *d) { /* mismatch */
  250.     if (!alloc) {
  251.       return 0L;
  252.     }
  253.     t  = new_trie(d+1,alloc);
  254.     t2 = new_trie(c+1,alloc);
  255.     t->datum=dict->datum;
  256.     t->table=dict->table;
  257.     dict->table= (trie **)new_trie_table(alloc->trie_tables);
  258.     dict->table[*c] = t2;
  259.     dict->table[*d] = t;
  260.     dict->datum =0L;
  261.     *d='\0';
  262.     return &(t2->datum);
  263.   }
  264.   
  265.   /*
  266.     Follow the pointers in table, if there are any
  267.     */
  268.   if (!dict->table) {
  269.     if (!alloc) {
  270.       return 0L;
  271.     }
  272.     dict->table=(trie **)new_trie_table(alloc->trie_tables);
  273.   }
  274.   
  275.   if(dict->table[*c]) {
  276.     return trie_lookup(c+1,dict->table[*c],alloc);
  277.   } else {
  278.     if (!alloc) {
  279.       return 0L;
  280.     }
  281.     dict->table[*c] = new_trie(c+1,alloc);
  282.     return &(dict->table[*c]->datum);
  283.   }
  284.  
  285. }
  286.  
  287. /*
  288.   WARNING: IF CHECK_ALNUM IS UNDEFINED, MAKE SURE YOU PASS IN AN ALNUM,
  289.   OR ELSE
  290. */
  291.  
  292. int encode( s)
  293. unsigned char* s; {
  294.   register unsigned char * e;
  295.   unsigned char t;
  296.   for(e=s;*e;e++) {
  297. #ifdef CHECK_ALNUM
  298.     if (!isalnum(*e)) {
  299.       return 0;
  300.     }
  301. #endif
  302.     if (isdigit(*e)) {
  303.       *e = *e -'0' + 27;
  304.     } else {
  305.       *e = (*e & 31);
  306.     }
  307.   }
  308.   return 1;
  309. }
  310.  
  311.  
  312. void decode(s) 
  313. unsigned char* s;
  314. {
  315.   while(*s) {
  316.     if (*s < 27) {
  317.       *s += ('a'-1);
  318.     } else {
  319.       *s += ('0'-27);
  320.     }
  321.     *s++;
  322.   }
  323. }
  324.